/********************************
 * Robinson Matrix Algorithm
 *
 * Copyright (C) 2009 CNRS
 * Author : Florent AVELLANEDA, Eugen CEPOI
 * 
 *
 * All rights reserved.
 *
 *   This file is part of Robinson Matrix Algorithm.
 *
 *   Robinson Matrix Algorithm is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   Robinson Matrix Algorithm is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with Robinson Matrix Algorithm.  If not, see <http://www.gnu.org/licenses/>.
 *
 ***********************************************************************************/
#include "TEST.h"
#include "Util.h"
#include "Var.h"
#include "SAT.h"
#include "AlgoGraph.h"
#include "Matrix.h"
#include "Algo.h"

#include <iostream>
#include <vector>
#include <set>
#include <stdlib.h>
#include <time.h>


bool test_calculateMaximalChain()
{

    for (unsigned int i = 2; i < 100; i++)
    {
        std::vector< std::set<unsigned int> > G;
        std::vector<unsigned int> result;

        G.resize( i*2*i*2 );

        for (unsigned int j = 1; j < i*2; j++)
            for (unsigned int k = 1; k < i*2; k++)
                G[j + k*i*2].insert( j+ (k-1)*i*2 );

        for (unsigned int j = 0; j < (i*2-1); j++)
            G[j*i*2].insert( (j+1)*i*2 );



        for (unsigned int j = 0; j < (i*2 - 1); j++)
            G[j*i*2].insert( j + j*i*2 + 1 );

        for (unsigned int j = 0; j < (i*2); j++)
            if(j!=1)
                G[j].insert(1);

        Util::calculateMaximalChain( G, 0, 1, result );

        if( result.size() != (i*2 + i*2 - 1) )
            return false;
    }

    return true;
}


bool pluspetit(unsigned int id, unsigned int val, unsigned int t, std::vector<unsigned int> &result, std::vector< std::set<unsigned int> > &graph, std::set<unsigned int> &S)
{
    if(S.count(id) == 0)
        return true;

    S.erase( id );

    if( val <= result[id] )
        return false;

    for (std::set<unsigned int>::iterator it = graph[id].begin(); it != graph[id].end(); ++it)
    {
        if(!pluspetit( *it, result[id], t, result, graph, S))
            return false;
    }

    return true;
}

bool test_topologicalSorting()
{
    for (unsigned int t = 3; t <= 100; t+=2)
    {
        std::vector< std::set<unsigned int> > graph;
        std::set<unsigned int> S;
        std::vector<unsigned int> result;
        std::vector<unsigned int> result2;

        graph.resize( t*t );

        for (unsigned int i = 0; i < t*t; i++)
            S.insert(i);

        for (unsigned int x = 0; x < t; x++)
        {
            for (unsigned int y = 0; y < t; y++)
            {
                if(x < (t/2))
                {
                    if(y < (t/2))
                    {
                        graph[x+t*y].insert( x+t*y+1 );
                    }else if(y > (t/2))
                    {
                        graph[x+t*y].insert( x+t*y-1 );
                    }
                }else if(x > (t/2))
                {
                    if(y < (t/2))
                    {
                        graph[x+t*y].insert( x+t*(y+1) );
                    }else if(y > (t/2))
                    {
                        graph[x+t*y].insert( x+t*(y-1) );
                    }
                }
            }
        }

        if( !AlgoGraph::topologicalSorting( graph, S, result ) )
        {
            std::cerr << "CYCLIQUE" << std::endl;
            return false;
        }

        result2.resize( result.size() );

        for (unsigned int i = 0; i < result.size(); i++)
        {
            result2[ result[i] ] = i;
        }

        while( S.size() > 0 )
            if(!pluspetit(*(S.begin()), result2[*(S.begin())]+1, t, result2, graph, S))
                return false;
    }




    return true;
}

bool test_stronglyConnected()
{
    for (unsigned int t = 4; t < 100; t+=10)
    {
        std::vector< std::set<unsigned int> > graph;
        std::set<unsigned int> S;
        std::vector<unsigned int> res;
        std::vector<std::set<unsigned int> > result;
        unsigned int aa, bb;

        graph.resize(t);
        for (unsigned int i = 0; i < t; i++)
            S.insert( i );

        unsigned int nb;

        while ( (nb = AlgoGraph::stronglyConnected( graph, S, res, result )) > (t/4) )
        {
            aa = rand() % t;
            do
            {
                bb = rand()%t;
            }
            while( bb == aa );
            graph[aa].insert( bb );
        }

        for (unsigned int i = 0; i < t; i++)
        {
            for (unsigned int j = 0; j < t; j++)
            {
                if(i==j)
                    continue;
                if( res[i] == res[j] )
                {
                    if( ! (AlgoGraph::existsPath( graph, i, j) && AlgoGraph::existsPath( graph, j, i ) ) )
                        return false;
                }
                else
                {
                    if( AlgoGraph::existsPath( graph, i, j ) && AlgoGraph::existsPath( graph, j, i ) )
                        return false;
                }
            }
        }
    }

    return true;
}

bool test_2SAT()
{
    unsigned int ia, ib;

    for (int i = 2; i <= 100; i++)
    {
        SAT::SAT sat;
        std::vector<std::pair<int, int> > clauses;
        std::vector<SAT::Var> var;
        std::vector<bool> b;

        var.reserve(i);
        for (int j = 0; j < i; j++)
            var.push_back( SAT::Var() );

        b.resize(i);
        for (int j = 0; j < i; j++)
            b[j] = (rand() % 2);

        for (int j = 0; j < (100*i/ (rand()%20+1)); j++)
        {
            ia = rand()%i;
            do
            {
                ib = rand()%i;
            }
            while( ib == ia );

            if(b[ia])
            {
                if(rand()%2)
                {
                    clauses.push_back( std::pair<int, int>( ia, ib ) );
                    sat.addClause( var[ia] + var[ib] );
                }
                else
                {
                    clauses.push_back( std::pair<int, int>( ia, -ib-1 ) );
                    sat.addClause( var[ia] + !var[ib] );
                }
            }else
            {
                if(rand()%2)
                {
                    clauses.push_back( std::pair<int, int>( -ia-1, ib ) );
                    sat.addClause( !var[ia] + var[ib] );
                }
                else
                {
                    clauses.push_back( std::pair<int, int>( -ia-1, -ib-1 ) );
                    sat.addClause( !var[ia] + !var[ib] );
                }
            }
        }

        if( !sat.solve2Sat() )
            return false;

        for (unsigned int j = 0; j < clauses.size(); j++)
        {

            if( (clauses[j].first < 0) && (clauses[j].second < 0) )
            {
                if ( var[-clauses[j].first-1].getVal() && var[-clauses[j].second-1].getVal() )
                    return false;
            }
            if( (clauses[j].first >= 0) && (clauses[j].second < 0) )
            {
                if (!var[clauses[j].first].getVal() && var[-clauses[j].second-1].getVal())
                    return false;
            }
            if( (clauses[j].first < 0) && (clauses[j].second >= 0) )
            {
                if (var[-clauses[j].first-1].getVal() && !var[clauses[j].second].getVal())
                    return false;
            }
            if( (clauses[j].first >= 0) && (clauses[j].second >= 0) )
            {
                if (!var[clauses[j].first].getVal() && !var[clauses[j].second].getVal())
                    return false;
            }
        }
    }
    return true;
}

namespace
{
    double dmax( double a, double b)
    {
        return (a<b)?b:a;
    }
}




double searchAndPrintBestMatrix(const Matrix &m, std::set<unsigned int> &list, std::vector<unsigned int> &order)
{
    double tmp;
    double best;
    best = -1;

    if( list.size() == 0 )
    {
        double delta;
        Algo::TotalOrder2RobinsonMatrix( m, order, delta );

        for (unsigned int i = 0; i < order.size(); i++)
            std::cerr << order[i] << " ";
        std::cerr << " = " << delta << std::endl;

        return delta;
    }

    for (std::set<unsigned int>::iterator it = list.begin(); it != list.end(); ++it)
    {
        std::set<unsigned int> list2(list);
        order.push_back( *it );
        list2.erase( *it );
        tmp = searchAndPrintBestMatrix( m, list2, order );
        order.pop_back();

        if((best==-1) || (tmp < best))
            best = tmp;
    }

    return best;
}


double searchBestMatrix(const Matrix &m, std::set<unsigned int> &list, std::vector<unsigned int> &order)
{
    double tmp;
    double best;
    best = -1;

    if( list.size() == 0 )
    {
        double delta;
        Algo::TotalOrder2RobinsonMatrix( m, order, delta );
        /* 
           for (unsigned int i = 0; i < order.size(); i++)
           std::cerr << order[i] << " ";
           std::cerr << " = " << delta << std::endl;
           */
        return delta;
    }

    for (std::set<unsigned int>::iterator it = list.begin(); it != list.end(); ++it)
    {
        std::set<unsigned int> list2(list);
        order.push_back( *it );
        list2.erase( *it );
        tmp = searchBestMatrix( m, list2, order );
        order.pop_back();

        if((best==-1) || (tmp < best))
            best = tmp;
    }

    return best;
}

double optimalRobinsonMatrixPrint(const Matrix &m)
{
    std::set<unsigned int> list;
    std::vector<unsigned int> order;

    for (unsigned int i = 0; i < m.getSize(); i++)
        list.insert(i);

    return searchAndPrintBestMatrix(m, list, order);
}


double optimalRobinsonMatrix(const Matrix &m)
{
    std::set<unsigned int> list;
    std::vector<unsigned int> order;

    for (unsigned int i = 0; i < m.getSize(); i++)
        list.insert(i);

    return searchBestMatrix(m, list, order);
}

Matrix generateTestMatrix( const Matrix &robinsonMatrix, double delta )
{
    std::vector<unsigned int> elements;
    elements.reserve(robinsonMatrix.getSize());
    for ( unsigned int i = 0; i < robinsonMatrix.getSize(); ++i )
        elements.push_back(i);

    std::vector<unsigned int> permutations;
    permutations.resize(robinsonMatrix.getSize());
    int i = 0;
    int ind;
    while( elements.size() > 0 )
    {
        ind = rand()%elements.size();
        permutations[i] = elements[ind];
        ++i;
        elements.erase(elements.begin()+ind);
    }

    return generateTestMatrix(robinsonMatrix, permutations, delta);
}

Matrix generateTestMatrix( const Matrix &robinsonMatrix, std::vector<unsigned int> &permutations, double delta )
{
    Matrix tmp = robinsonMatrix;
    for ( unsigned int i = 0; i < robinsonMatrix.getSize(); ++i )
        for ( unsigned int j = (i+1); j < robinsonMatrix.getSize(); ++j )
            if ( delta <= tmp.get(i,j) )
                tmp.set( i, j, tmp.get(i, j) - delta );
            else
                tmp.set( i, j, 0);

    Matrix m = tmp;
    if ( permutations.size() != m.getSize() )
        return m;

    for ( unsigned int i = 0; i < permutations.size(); ++i )
        for ( unsigned int j = (i+1); j < permutations.size(); ++j )
            m.set(i,j, tmp.get(permutations[i],permutations[j]));

    return m;
}

bool test()
{
    bool result = true;

    std::cerr << "TEST calculateMaximalChain" << std::endl;
    if( !test_calculateMaximalChain() )
    {
        std::cerr << "ECHEC" << std::endl;
        result = false;
    }
    else
        std::cerr << "OK" << std::endl;

    std::cerr << "TEST topologicalSorting" << std::endl;
    if( !test_topologicalSorting() )
    {
        std::cerr << "ECHEC" << std::endl;
        result = false;
    }else
        std::cerr << "OK" << std::endl;

    std::cerr << "TEST stronglyConnected" << std::endl;
    if( !test_stronglyConnected() )
    {
        std::cerr << "ECHEC" << std::endl;
        result = false;
    }else
        std::cerr << "OK" << std::endl;

    std::cerr << "TEST 2SAT" << std::endl;
    if( !test_2SAT() )
    {
        std::cerr << "ECHEC" << std::endl;
        result = false;
    }
    else
        std::cerr << "OK" << std::endl;

    return result;
}
